#include <vector>
using namespace std;


// version 1
class Solution {
public:
    int GetLastWriteNumPos(vector<int>& arr, int* dest){
        int len = 0, pos = 0;
        while(pos < arr.size()){
            len += (arr[pos] == 0) ? 2 : 1;
            if(len >= arr.size()) break;
            ++pos;
        }

        //这里再做的工作就是：
        //去模拟一下原数组中被复写到新数组的情况:(先假设异地修改)
        //如果说被复写的新数组还剩两个空位，不用怕
        //但是因为0的特殊性
        //当只剩下最后一个位置时候，碰到0就会出问题
        //表现的状况就是 len > arr.size()
        //这个时候，我们就知道，复写过程中，最后一个为0，且只能写一次！因为再写就越界了！

        if(len > arr.size()) arr[(*dest)] = 0;
        //处理方法很简单，所以，既然知道最后一个复写位置可能出问题，那就特殊处理
        //一旦发生上述情况，就知道最后一个复写位置必然0 -> arr[(*dest)] = 0
        //传进来的dest就是数组最后一个位置。

        *dest = (len == arr.size()) ? arr.size() - 1 : arr.size() - 2;
        return (len == arr.size()) ? pos : pos - 1;
        //然后处理一下正常开始复写的位置 和正常被复写的位置！
    }


    void duplicateZeros(vector<int>& arr) {
        int dest = arr.size() - 1;
        int src = GetLastWriteNumPos(arr, &dest);
        //这里是怕 数组 [0] 这样的情况出现，导致dest < 0越界
        while(src >= 0 && dest >= 0){
            if(arr[src] == 0) arr[dest--] = arr[src];
            arr[dest--] = arr[src--];
        }
    }
};